#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/23 17:03
# ===========================================
#       题目名称： 32. 最长有效括号
#       题目地址： https://leetcode.cn/problems/longest-valid-parentheses/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
import time


class Solution:
    """
        实现思路：
         我们只需要明确一个问题，即什么样的模式是合格的，什么样的模式是不合格的。这两个条件决定了我们入栈和出栈的规则。

合格的模式应该是有序且成对的()，即(...)

不合格的模式应该是无序的，不管他成对不成对，即)...(，或者(...(, 或者)...)

所以我们的栈需要对比当前字符，如果满足有序成对，则出栈，出栈时不断更新合格的长度即可。
    """

    def longestValidParentheses(self, s):
        stack = []  # 构建一个栈记录字符index
        ans = 0
        for i in range(len(s)):
            print(stack)
            # 如果栈非空，且当前为右括号，且有记录的左括号，则出栈
            if stack and s[i] == ")" and s[stack[-1]] == "(":
                stack.pop()
                # 如果出栈后变成空栈，则说明整个[0:i]的区间都是合格的，长度为i+1
                # 如果出栈后非空，则说明区间[stack[-1]:i]是合格的
                ans = max(ans, i - (stack[-1] if stack else -1))
            else:
                # 以下3个条件会触发else
                # 如果是空栈
                # 或者当前字符为左括号（需要寻找匹配的右括号）
                # 或者当前字符为右括号，而且栈顶记录的也是右括号（不合格的情况，永远不会被pop）
                stack.append(i)

        return ans

    def longestValidParentheses3(self, s):
        s_time = time.time()
        max_val = 0  # 最长的值
        if not s:
            return max_val
        # 定义左右双指针
        left, right = 0, 1 + max_val
        while left < right < len(s):
            # print(left , right , max_val)
            if right - left > max_val:  # 剔除比最大值小的区间
                temp_s = s[left: right + 1]
                if temp_s and not temp_s.startswith(")") and not temp_s.endswith("("):
                    while temp_s and temp_s.find("()") != -1:
                        temp_s = temp_s.replace("()", "")
                    if not temp_s:
                        max_val = max(right + 1 - left, max_val)

            if right + 1 > len(s) - 1:
                left += 1
                right = left + 1 + max_val
            else:
                right += 1
        print("消耗时长：", time.time() - s_time)
        return max_val

    def longestValidParentheses2(self, s):
        """
            效率有问题
        """
        s_time = time.time()
        max_val = 0  # 最长的值
        if not s:
            return max_val
        # 定义左右双指针
        left, right = 0, len(s) - 1
        while left < right < len(s):
            if right - left > max_val:  # 剔除比最大值小的区间
                temp_s = s[left: right + 1]
                if temp_s and temp_s[0] != ")" and temp_s[-1] != "(":
                    while temp_s and temp_s.find("()") != -1:
                        temp_s = temp_s.replace("()", "")
                    if not temp_s:
                        max_val = max(right + 1 - left, max_val)
            if len(s) - left <= max_val:  # 当前到最后的是否比最大值要小
                break
            if right - 1 - left < max_val or right - 1 == left:
                left += 1
                right = len(s) - 1
            else:
                right -= 1
        print("消耗时长：", time.time() - s_time)
        return max_val


if __name__ == '__main__':
    s = Solution()
    # 2
    print(s.longestValidParentheses(s="(()"))
    # 4
    print(s.longestValidParentheses(s=")()())"))
    # 0
    print(s.longestValidParentheses(s=""))
    # 6
    print(s.longestValidParentheses(s="()(())"))
    # 168
    print(s.longestValidParentheses(
        s="((())())(()))(()()(()(()))(()((((()))))))((()())()))()()(()(((((()()()())))()())(()()))((((((())))((()))()()))))(()))())))()))()())((()()))))(()(((((())))))()((()(()(())((((())(())((()()(()())))())(()(())()()))())(()()()))()(((()())(((()()())))(((()()()))(()()))()))()))))))())()()((()(())(()))()((()()()((())))()(((()())(()))())())))(((()))))())))()(())))()())))())()((()))((()))()))(((())((()()()(()((()((())))((()()))())(()()(()))))())((())))(()))()))))))()(()))())(()())))))(()))((())(()((())(((((()()()(()()())))(()())()((()(()()))(()(())((()((()))))))))(()(())()())()(()(()(()))()()()(()()())))(())(()((((()()))())))(())((()(())())))))())()()))(((())))())((()(()))(()()))((())(())))))(()(()((()((()()))))))(()()()(()()()(()(())()))()))(((()(())()())(()))())))(((()))())(()((()))(()((()()()(())()(()())()(())(()(()((((())()))(((()()(((()())(()()()(())()())())(()(()()((()))))()(()))))(((())))()()))(()))((()))))()()))))((((()(())()()()((()))((()))())())(()((()()())))))))()))(((()))))))(()())))(((()))((()))())))(((()(((())))())(()))))(((()(((((((((((((())(((()))((((())())()))())((((())(((())))())(((()))))()())()(())())(()))))()))()()()))(((((())()()((()))())(()))()()(()()))(())(()()))()))))(((())))))((()()(()()()()((())((((())())))))((((((()((()((())())(()((()))(()())())())(()(())(())(()((())((())))(())())))(()()())((((()))))((()(())(()(()())))))))))((()())()()))((()(((()((()))(((((()()()()()(()(()((()(()))(()(()((()()))))()(()()((((((()((()())()))((())()()(((((()(()))))()()((()())((()())()(())((()))()()(()))"))
